The present invention relates to an identification scheme based on security according to difficulty in calculating discrete logarithms, and a digital signature scheme giving message recovery and a digital signature scheme with appendix for authenticating each identity processing information, protecting the integrity of transferred information and preventing fraudulent information processing behavior.
A digital signature corresponding to a conventional manual signature is used to confirm a communicating counterpart, to prevent the unauthorized modification of the communication contents and to solve a dispute about communication behavior. A method for generating the digital signature can be classified into a digital signature scheme with appendix and a digital signature scheme giving message recovery, according to forms and functions of the generated digital signature.
Assuming that p is a large prime number, q is another prime number for dividing p-1, g is a natural number having a remainder 1 obtained by dividing its q.sup.th power by p, g being between 1 and p, then g, q and p are system coefficients commonly utilized by users. If each user randomly selects a natural number s between 1 and q as a secret key and uses, as a public key, a remainder v (.tbd.g.sup.-s mod p) obtained by dividing the -s.sup.th power of g by p, public coefficients used by each user are v, g, q and p.
It is hard to find out the secret key s from these public coefficients and therefore it is equivalent that a problem of discrete logarithms is difficult to calculate. Numerous public key identification schemes and digital signature schemes are based on security strength from the fact that the problem of the discrete logarithms is difficult to calculate.
Schnorr published the identification scheme and the digital signature scheme based on the security of the discrete logarithms in 1989. The digital signature scheme published by Schnorr, which is the digital signature scheme with appendix, introduces a hash compression function to the digital signature scheme published by Elgamal in 1985, and simplifies the procedure for generating and verifying the digital signature. Moreover, the generated digital signature is small in size.
The identification scheme proposed by Schnorr uses the same logarithm structure as the digital signature scheme, and authenticates one's own identity to a communicating counterpart.
The identification scheme proposed by Schnorr in which a prover A authenticates his identity to a verifier B will now be described.
If the prover's system coefficients are g, q and p, the secret key is s (1&lt;s&lt;q), and the public key is v (.tbd.g.sup.-s mod p), the prover A selects a random number r between 1 and g and transmits a remainder x (.tbd.g.sup.r mod p) obtained by dividing the r.sup.th power of g by p to the verifier B. If x is received from the prover A, the verifier B selects a random number e between 1 and q and transmits the number e to the prover A. The prover A multiplies the random number e received from the verifier B by the secret key s and adds the random number r, to yield r+se. The prover A transmits a remainder y (.tbd.r+se mod q) obtained by dividing r+se by q to the verifier B. If y is received from the prover A, the verifier B calculates a remainder x' (.tbd.g.sup.y v.sup.e mod p) obtained by dividing the product of the y.sup.th power of g and the e.sup.th power of v by p. The verifier B authenticates the validation of prover's identity by confirming whether x' and x are identical to each other.
In the digital signature scheme with appendix proposed by Schnorr, if a message to be signed is m, a signer A selects a random number r between 1 and q and calculates a remainder x (.tbd.g.sup.r mod p) obtained by dividing the r.sup.th power of g by p. The message m and the calculated x are applied to the hash function to yield e (=h(x, m)). The signer A calculates a remainder y (.tbd.r+se mod q) obtained by dividing r added to the product of s and e by q. Then (e, y) is the digital signature with appendix for the message m. The validation of the digital signature (e, y) with appendix for the message m is easily verified since a singer's public key is known.
That is, if the digital signature with appendix of the signer A for the message m is (e, y), the verifier B calculates a remainder x' (.tbd.g.sup.y v.sup.e mod p) obtained by dividing the product of the y.sup.th power of g and the e.sup.th power of v by p. The remainder x' and the message m are applied to the hash function to yield e' (=h(x', m). The validation of the digital signature (e, y) with appendix of the signer A is verified by confirming whether e' and e are the same.
Meanwhile, Nyberg and Rueppel published the digital signature scheme giving message recovery based on security of the discrete logarithms in 1993. The digital signature scheme giving message recovery of N-R (Nyberg-Rueppel) will now be described.
It is assumed that the signer's system coefficients are g, q and p, the secret key is s (1&lt;s&lt;q), the public key is v (.tbd.g.sup.-s mod p), and the message to be signed is m, m being a natural number which is greater than or equal to 1, and less than or equal to the prime number p. The signer selects a random number r between 1 and q, and calculates a remainder x (.tbd.mg.sup.-r mod p) obtained by dividing the product of the message m and the -r.sup.th power of g by p. The singer adds r to the secret key s multiplied by x to yield r+sx and calculates a remainder y (.tbd.r+sx mod q) obtained by dividing r+sx by q. Then (x, y) is the digital signature giving message recovery for the message m.
To verify the digital signature (x, y), the verifier calculates a remainder(.tbd.xg.sup.y v.sup.x mod p) obtained by dividing the product of x and the y.sup.th power of g and the x.sup.th power of v by p, to recover the message m. The verifier verifies the validation of the digital signature (x, y) by confirming the contents of the recovered message m.
However, the digital signature with appendix generates only the digital signature for the message. In the digital signature giving message recovery, if the message to be signed is larger in size than p, the message m should be divided into various messages smaller than p. Since the digital signature is generated for the divided messages, the size of the generated digital signature is increased.